#include "Tree.h"


// 方法一
class Solution {
public:

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;

        int pos = 0, n = preorder.size();
        while (inorder[pos] != preorder[0])pos += 1; //找到中序遍历中的根节点位置
        TreeNode* root = new TreeNode(preorder[0]);

        vector<int> preArr;// 存储前序遍历的结果
        vector<int> inArr; // 存储中序遍历的结果

        //获得根节点的左子树
        for (int i = 1; i <= pos; i++) preArr.push_back(preorder[i]); //前序遍历左子树的结果
        for (int i = 0; i <= pos; i++) inArr.push_back(inorder[i]); //中序遍历左子树的结果
        root->left = buildTree(preArr, inArr);

        preArr.clear();
        inArr.clear();

        //获得根节点的右子树
        for (int i = pos + 1; i < n; i++) preArr.push_back(preorder[i]); //前序遍历右子树的结果
        for (int i = pos + 1; i < n; i++) inArr.push_back(inorder[i]); //中序遍历右子树的结果
        root->right = buildTree(preArr, inArr);

        return root;
    }
};



// 方法二
class Solution {
public:
    void BuildTree(TreeNode* &t, vector<int> pre, int pre_low, vector<int> in, int in_low, int len)
    {
        /****在此下面完成代码************/
        t = new TreeNode;
        if (t != NULL)
        {
            if (len <= 0) { //递归截止
                t = NULL;
                return;
            }
            int index = 0;
            while (index < len && pre[pre_low] != in[in_low + index]) index++; //寻找当前的root结点（包含子树）
            t->val = pre[pre_low];
            BuildTree(t->left, pre, pre_low + 1, in, in_low, index);//去掉root结点
            BuildTree(t->right, pre, pre_low + 1 + index, in, in_low + 1 + index, len - (index + 1));//去掉左边和根节点
        }
    }
    /*********************************/
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* t;
        int n = preorder.size();
        BuildTree(t, preorder, 0, inorder, 0, n);
        return t;
    }
};